package arrAndstr;

import java.util.HashSet;
import java.util.Set;

/*
    36. 有效的数独
 */
public class T36 {
    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'.', '.', '4', '.', '.', '.', '6', '3', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'5', '.', '.', '.', '.', '.', '.', '9', '.'},
                {'.', '.', '.', '5', '6', '.', '.', '.', '.'},
                {'4', '.', '3', '.', '.', '.', '.', '.', '1'},
                {'.', '.', '.', '7', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '5', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}
        };
        System.out.println(isValidSudoku(board));
    }

    public static boolean isValidSudoku(char[][] board) {
        int row = board.length;
        int column = board[0].length;

        for (int i = 0; i < row; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < column; j++) {
                char ch = board[i][j];
                if ((ch <= '9' && ch >= '0') && !set.contains(ch)) {
                    set.add(ch);
                } else if (set.contains(ch)) {
                    return false;
                }
            }
        }

        for (int i = 0; i < column; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < row; j++) {
                char ch = board[j][i];
                if ((ch <= '9' && ch >= '0') && !set.contains(ch)) {
                    set.add(ch);
                } else if (set.contains(ch)) {
                    return false;
                }
            }
        }

        // 块
        for (int i = 0; i < row; i += 3) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < column; j += 3) {
                boolean isShuDu = blockIsShuDu(board, i, j);
                if (!isShuDu) {
                    return false;
                }
            }
        }

        return true;
    }

    // 判断方格内，(x0, y0) --> 左上角下标
    private static boolean blockIsShuDu(char[][] board, int x0, int y0) {
        Set<Character> set = new HashSet<>();
        for (int i = x0; i < x0 + 3; i++) {
            for (int j = y0; j < y0 + 3; j++) {
                char ch = board[i][j];
                if ((ch <= '9' && ch >= '0') && !set.contains(ch)) {
                    set.add(ch);
                } else if (set.contains(ch)) {
                    return false;
                }
            }
        }

        return true;
    }
}
